//
// Created by LiuYou on 2021/12/6.
//

#include <iostream>
#include <vector>
#include <random>
#include <iterator>
#include <algorithm>


namespace heap {


    static int random(int left, int right) {
        std::random_device randomDevice;
        std::default_random_engine randomEngine( randomDevice());
        std::uniform_int_distribution<> uniformIntDistribution( left, right );
        return uniformIntDistribution( randomEngine );
    }


    class MaxHeap {
    public:
        static void heapSort(std::vector<int>& arr) {
            if (arr.empty() || arr.size() == 1) {
                return;
            }

            int heapSize = arr.size();
            makeHeap( arr );

            while (heapSize > 0) {
                std::swap( arr[0], arr[--heapSize] );
                heapify( arr, 0, heapSize );
            }
        }

        static void makeHeap(std::vector<int>& arr) {
            // 下面的这两个 for循环 都可以构建一个大顶堆。
//            for (int i = arr.size() - 1; i >= 0; --i) {
//                heapify( arr, i, arr.size());
//            }

            for (int i = 0; i < arr.size(); ++i) {
                heapInsert( arr, i );
            }

        }

    private:
        /**
         * @brief 从下标索引 idx 开始, 构建为一个大顶堆。
         * @param arr
         * @param idx
         */
        static void heapify(std::vector<int>& arr, int idx, int heapSize) {
            int leftChildIdx = idx * 2 + 1;
            while (leftChildIdx < heapSize) {
                int greatestIdx = leftChildIdx;
                if ((leftChildIdx + 1 < heapSize) && arr[leftChildIdx + 1] > arr[leftChildIdx]) {
                    greatestIdx = leftChildIdx + 1;
                }
                if (arr[greatestIdx] > arr[idx]) {
                    std::swap( arr[greatestIdx], arr[idx] );
                    idx = greatestIdx;
                    leftChildIdx = idx * 2 + 1;
                } else {
                    break;
                }
            }
        }

    public:
        /**
         * @brief 从 idx 开始构建大顶堆。
         * @param arr
         * @param idx
         */
        static void heapInsert(std::vector<int>& arr, int idx) {
            int parentIdx = (idx - 1) / 2;
            while (parentIdx >= 0) {
                if (arr[idx] > arr[parentIdx]) {
                    std::swap( arr[idx], arr[parentIdx] );
                    idx = parentIdx;
                    parentIdx = (idx - 1) / 2;
                } else {
                    break;
                }
            }
        }
    };


    class MinHeap {
    public:
        static void heapSort(std::vector<int>& arr) {
            if (arr.empty() || arr.size() == 1) {
                return;
            }

            int heapSize = arr.size();
            makeHeap( arr );

            while (heapSize > 0) {
                std::swap( arr[0], arr[--heapSize] );
                heapify( arr, 0, heapSize );
            }
        }

        static void makeHeap(std::vector<int>& arr) {
//            for (int i = arr.size() - 1; i >= 0; --i) {
//                heapify( arr, i, arr.size());
//            }

            for (int i = 0; i < arr.size(); ++i) {
                heapInsert( arr, i );
            }
        }

    private:
        /**
         * @brief 从下标索引 idx 开始, 构建为一个小顶堆。
         * @param arr
         * @param idx
         */
        static void heapify(std::vector<int>& arr, int idx, int heapSize) {
            int leftChildIdx = idx * 2 + 1;
            while (leftChildIdx < heapSize) {
                int leastIdx = leftChildIdx;
                if ((leftChildIdx + 1 < heapSize) && arr[leftChildIdx + 1] < arr[leftChildIdx]) {
                    leastIdx = leftChildIdx + 1;
                }
                if (arr[leastIdx] < arr[idx]) {
                    std::swap( arr[leastIdx], arr[idx] );
                    idx = leastIdx;
                    leftChildIdx = idx * 2 + 1;
                } else {
                    break;
                }
            }
        }

    public:
        /**
         * @brief 从 idx 开始构建小顶堆。
         * @param arr
         * @param idx
         */
        static void heapInsert(std::vector<int>& arr, int idx) {
            int parentIdx = (idx - 1) / 2;
            while (parentIdx >= 0) {
                if (arr[idx] < arr[parentIdx]) {
                    std::swap( arr[idx], arr[parentIdx] );
                    idx = parentIdx;
                    parentIdx = (idx - 1) / 2;
                } else {
                    break;
                }
            }
        }
    };
}


using namespace heap;


int main(int argc, char** argv) {
    {
        std::vector<int> arr( 10 );
        for (auto& item: arr) {
            item = random( 0, 100 );
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;

        MinHeap::heapSort( arr );
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::boolalpha << std::is_sorted( arr.begin(), arr.end(), std::greater<>());
        std::cout << std::endl;

        MinHeap::makeHeap( arr );
        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::boolalpha << std::is_heap( arr.begin(), arr.end(), std::greater<>());
        std::cout << std::endl;
    }

    std::cout << "===================================================" << std::endl;
    {
        std::vector<int> arr( 10 );
        for (auto& item: arr) {
            item = random( 0, 100 );
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;

        MaxHeap::heapSort( arr );

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::boolalpha << std::is_sorted( arr.begin(), arr.end());
        std::cout << std::endl;
    }


    return 0;
}
